import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class day230414 {
    // 计算字符串的编辑距离
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            char[] A= sc.nextLine().toCharArray();
            char[] B = sc.nextLine().toCharArray();
            int m = A.length;
            int n = B.length;
            // 多定义一行,一列
            int[][] dp = new int[m + 1][n + 1];

            // 初始化
            // 第一行表示, 空串变为 A的前i个字符 的编辑距离
            for (int i = 0; i <= n; i++) {
                dp[0][i] = i;
            }

            //       a b c d e
            //    0  1 2 3 4 5
            // a  1
            // b  2
            // c  3
            // d  4
            // e  5

            // 第一列表示, B的前i个字符 变为空串 的编辑距离
            for (int i = 0; i <= m; i++) {
                dp[i][0] = i;
            }

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (A[i - 1] == B[j - 1]) {
                        // 相等, 编辑距离不变
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // 不相等, 编辑距离在插入,替换,删除中选择最小值
                        int min = Math.min(dp[i][j - 1], dp[i - 1][j]);
                        dp[i][j] = Math.min(min, dp[i - 1][j - 1]) + 1;
                    }
                }
            }

            System.out.println(dp[m][n]);
        }
    }

    // 微信红包

    // o(n)
    public int getValue(int[] gifts, int n) {
        // 将数组排序
        Arrays.sort(gifts);
        // 获取中间数据
        int mid = gifts[n / 2];
        // 如果右超过一半的数据, 那么一定在中间

        // 遍历数组, 看中间数据是否超过一半
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (mid == gifts[i]) {
                count++;
            }
        }
        if (count > n/2) {
            return mid;
        }
        return 0;
    }


    // 通过 HashMap 计数，遍历数组计数, 然后遍历 HashMap, o(n)
    public int getValue1(int[] gifts, int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(gifts[i], map.getOrDefault(gifts[i], 0) + 1);
        }

        for (int i = 0; i < n; i++) {
            if (map.get(gifts[i]) > n / 2) {
                return gifts[i];
            }
        }
        return 0;
    }
}
